import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: MENG
 * Date: 2022-07-21
 * Time: 20:49
 */
public class Sort {
    /**
     * 直接插入排序
     * 时间复杂度：
     *      最坏：O(n^2)  逆序
     *      最好：O(n)    有序
     *      结论：对于直接插入排序来说，数据越有序越快。
     *      场景：当数据基本上是有序的时候，使用直接插入排序
     * 空间复杂度：O(1)
     * 稳定性：稳定
     *       一个本身就稳定的排序 ，你可以实现为不稳定
     *       但是一个本身就不稳定的排序，你没有办法变成稳定的排序
     * @param
     */
    public static void insertSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            //=0的情况也要判断
            for (; j >= 0; j--) {
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }

    }
    /**
     * 希尔排序的时间复杂度：
     * O(N^1.3 - N^1.5)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    private static void shell(int [] array,int gap) {
        //这里一定要++
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0 ; j -= gap) {
                if(array[j] > tmp){
                    array[j+gap] = array[j];
                }else{
                    break;
                }
            }
            array[j+gap] = tmp;
        }

    }

    //希尔排序的增量
    public static void shellSort(int[] array){
        int gap = array.length;
        while(gap > 1){
            shell(array,gap);
            gap /= 2;
        }
        //最后在整体排序一次即可。
        shell(array,1);

    }

    /**
     * 直接选择排序
     * 时间复杂度：O(n^2) -> 对数据不敏感 不管你是有序的还是无序的 时间复杂度都是这样的
     * 空间复杂度：O(1)
     * 稳定性：不稳定的排序
     * @param array
     */

    //交换方法
    private static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[minIndex]){
                    minIndex = j;
                }
            }
            swap(array,minIndex,i);
        }
    }

    //改进版选择排序
    public static void selectSort2(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while(left < right){
            int minIndex = left;
            int maxIndex = left;
            for (int i = left+1; i <= right; i++) {
               if(array[i] < array[minIndex] ){
                   minIndex = i;
               }
               if(array[i] > array[maxIndex]){
                   maxIndex = i;
               }
            }

            swap(array, minIndex,left);
            if(left == maxIndex){
                maxIndex = minIndex;
            }
            swap(array,maxIndex,right);
            left++;
            right--;
        }

    }

    /**
     *堆排序
     * 时间复杂度：O(n*logn) 10240
     * N^0.5    logn
     * 空间复杂度：O(1)
     * 稳定性：不稳定的
     * @param
     */

    //堆排
    public static void heapSort(int[] array) {
        createBigHeap(array);
        int end = array.length - 1;
        while (end >=0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }

    //创建大根堆
    private static void createBigHeap(int[] array){
        for (int parent = (array.length -1-1)/2; parent >= 0 ; parent--) {
            shiftDown(array,parent,array.length);
        }
    }

    //向下调整
    private static void shiftDown(int[] array,int parent,int len){
        int child = parent * 2 + 1;
        //有左孩子
        while(child < len){
            if(child + 1 < len && array[child] < array[child+1]){
                child++;
            }
            if(array[child] > array[parent]){
                swap(array,child,parent);
                parent = child;
                child = 2 * parent +1;
            }else{
                break;
            }
        }
    }
    /**
     * 冒泡排序
     * 时间复杂度：O(N^2)
     *     针对优化后的代码，时间复杂度在有序的情况下：O(n)
     * 空间复杂度：O(1)
     * 稳定性：稳定 的排序
     * 插入
     * @param array
     */

    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]){
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            if (!flg){
                break;
            }
        }
    }

    //快速排序
    /**
     * Hoare法  找基准
     * @param array
     * @param start
     * @param end
     * @return
     */
    private static int partitionHoare(int[] array,int start,int end){
        int i = start;
        int key = array[start];
        while(start < end){
            while (start < end && array[end] >= key){
                end--;
            }
            while(start < end && array[start] <= key){
                start++;
            }
            swap(array,start,end);
        }
        swap(array,start,i);
        return start;
    }

    /**
     * 挖坑法
     * @param array
     * @param start
     * @param end
     * @return
     */
    private static int partitionHole(int[] array,int start,int end){
        int key = array[start];
        while (start < end){
            while(start < end && array[end] > key){
                end--;
            }
            array[start] = array[end];
            while (start < end && array[start] < key){
                start++;
            }
            array[end] = array[start];
        }
        //start和end相遇了
        array[start] = key;
        return start;
    }


    /**
     * 前后指针法
     * @param array
     * @param start
     * @param end
     * @return
     */
    private static int partition(int[] array,int start,int end) {
        //start没动
        int prev = start;
        int cur = start+1;
        while (cur <= end){
            if(array[cur] < array[start] && array[++prev] != array[cur]){
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,start);
        return prev;
    }

    public static void quickSort(int[] array,int left,int right) {
        if(left >= right){
            return;
        }
        int pivot = partition(array,left,right);
        quickSort(array,left,pivot-1);
        quickSort(array,pivot+1,right);
    }

    /**
     * 三数取中
     * @param array
     * @param left
     * @param right
     * @return
     */

    private static int midNumIndex(int[] array,int left,int right) {
        int mid = (right + left)/2;
        if(array[left] < array[right]){
            if(array[mid] < array[left]){
                return left;
            }else if(array[mid] > array[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[mid] < array[right]){
                return right;
            }else if(array[mid] > array[left]){
                return left;
            }else{
                return mid;
            }
        }
    }
    public static void quickSortThree(int[] array,int left,int right) {
        if(left >= right){
            return;
        }
        int index = midNumIndex(array,left,right);
        swap(array,index,left);
        int pivot = partition(array,left,right);
        quickSort(array,left,pivot-1);
        quickSort(array,pivot+1,right);
    }

    //为了减少快排的递归次数，重写插入排序方法
    public static void insertSortDeep(int[] array,int start,int end){
        for (int i = start + 1; i <= end ; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >=start ; j--) {
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    public static void quickSortDeep(int[] array,int left,int right) {
        if(left >= right){
            return;
        }
        if(right-left+1 <= 7){
            insertSortDeep(array,left,right);
            return;
        }

        int index = midNumIndex(array,left,right);
        swap(array,index,left);
        int pivot = partition(array,left,right);
        quickSort(array,left,pivot-1);
        quickSort(array,pivot+1,right);
    }

    /**
     * 非递归实现 快速排序,重写quickSort方法，所以不报错
     * @param array
     */
    public static void quickSort(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length - 1;
        //调用三数取中来找pivot基准值
        int index = midNumIndex(array,left,right);
        swap(array,index,left);
        int pivot =partitionHoare(array,left,right);

        //检测左边是否只有一个元素了
        if(pivot > left + 1){
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot < right - 1){
            stack.push(pivot + 1);
            stack.push(right);
        }
        //检查栈是否是空栈，空的话就已经有序了
        while(!stack.empty()){
            //作为新的区间来找基准值
            right = stack.pop();
            left = stack.pop();
            index = midNumIndex(array,left,right);
            swap(array,index,left);
            pivot = partitionHoare(array,left,right);
            if(pivot > left+1) {
                stack.push(left);
                stack.push(pivot - 1);
            }
            if(pivot < right-1) {
                stack.push(pivot + 1);
                stack.push(right);
            }

        }
    }
    /**
     * 归并排序
     * 时间复杂度：O(n*logn)
     * 空间复杂度：O(n)
     * 稳定性：稳定排序
     *   直接插入  冒泡  归并
     * @param array
     */
    public static void mergeSort(int[] array,int left,int right) {
        if(left >= right){
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(array,left,mid);
        mergeSort(array,mid + 1,right);
        merge(array,left,right,mid);
    }

    private static void merge(int[] array,int start,int end,
                              int midIndex) {
        int[] tmpArray = new int[end - start +1];
        int k = 0;//新数组的下标
        int s1 = start;
        int s2 = midIndex+1;
        while(s1 <= midIndex && s2 <= end ){
            if(array[s1] <= array[s2]){
                tmpArray[k++] = array[s1++];
            }else{
                tmpArray[k++] = array[s2++];
            }
        }
        while(s1 <= midIndex){
            tmpArray[k++] = array[s1++];
        }
        while(s2 <= end){
            tmpArray[k++] = array[s2++];
        }

        for (int i = 0; i < k; i++) {
            array[i+start] = tmpArray[i];
        }
    }
    //非递归实现归并排序
    public static void mergerSortNotRecur(int[] array) {
        int gap = 1;
        //未排序完，进入while循环
        while(gap < array.length){
            //注意i的步进
            for (int i = 0; i < array.length; i+=gap*2) {
                int s1 = i;
                int e1 = s1 + gap - 1;
                if(e1 >= array.length){
                    e1 = array.length -1;
                }

                int s2 = e1 +1;
                if(s2 >= array.length){
                    s2 = array.length-1;
                }

                int e2 = s2 + gap - 1;
                if(e2 >= array.length){
                    e2 = array.length - 1;
                }
                merge(array,s1,e2,e1);
            }
            //下一次的gap为上一次的2倍
            gap *= 2;
        }

    }

    /**
     * 时间复杂度：O(N+范围)
     * 空间复杂度：O(范围)
     * 稳定性：
     * 计数排序：适合 给定一个范围的数据 进行排序
     * @param array
     */

    public static void countSort(int[] array) {
        int minVal = array[0];
        int maxVal = array[1];
        for (int i = 0; i < array.length; i++) {
            if(array[i] < minVal){
                minVal = array[i];
            }
            if(array[i] > maxVal){
                maxVal = array[i];
            }
        }
        int len = maxVal - minVal + 1;
        int[] count = new int[len];
        for (int i = 0; i < array.length; i++) {

            int val = array[i];
            count[val - minVal]++;
        }
        int index = 0;//记录array数组的下标
        for (int i = 0; i < count.length; i++) {
            while(count[i]!=0){
                array[index] = i + minVal;
                index++;
                count[i]--;
            }
        }
    }

}























